This invention relates to the field of computer systems. More particularly, a method and apparatus are provided for determining which portion of a TCP (Transport Control Protocol) sequence space the contents of a TCP packet land in.
Information (e.g., data, packets, cells) sent or received over an electronic communication connection is often numbered and tracked. Incoming data may then be compared to what was expected, to ensure sequential processing of the data, to verify that all information is received, to identify duplicate or corrupted data, or for some other purpose.
For example, data transmitted via a TCP connection is sequentially numbered (by byte); each TCP packet identifies the sequence numbers of the data bytes it conveys. Illustratively, a packet header may identify the sequence number of the first or last byte of TCP data in the packet, along with the total amount of data.
Based on the sequence numbers of data previously received over a given TCP connection, the recipient may determine (by sequence number) what data should be received next. If the sequence numbers of the contents of the next packet fall within the range of expected sequence numbers (e.g., the sequence numbers immediately following those of the previous packet), the packet may be considered to fall “in-zone.” If the sequence numbers fall outside the expected range, the packet may be considered to fall “out-of-zone.” An out-of-zone packet or sequence number may indicate a packet that is out-of-order, corrupted, a duplicate, etc. Out-of-zone packets need to be identified because they may require special processing by the recipient.
A TCP sequence numbering scheme is circular in nature, in that it starts at zero and wraps around from a maximum value back to zero. The TCP sequence space may be divided in half, with one half representing in-zone sequence numbers and the other half out-of-zone sequence numbers. Because the range of expected or in-zone sequence numbers changes with each TCP data packet received, the zones change for each data packet.
The TCP sequence space may be divided by selecting some sequence number as an anchor or starting point, and adding half the maximum sequence number. The sum represents a relative midpoint in the sequence space, between the selected anchor and the point at which the sequence numbers would wrap around to the anchor. The in-zone range comprises sequence numbers greater than the anchor and less than the midpoint, while the out-of-zone range of sequence numbers comprises sequence numbers greater than the midpoint and less than the anchor.
Traditionally, an adder was employed to generate the relative midpoint. However, due to the size of TCP sequence numbers (32 bits) such an adder is large (i.e., 33 bits) and requires substantial logic. And, with the ever-increasing data rates, computation of the midpoint for each packet becomes a bottleneck in the processing of incoming TCP packets, thereby limiting the effective throughput.